package offerbook;

/**
 * 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，
 * <p>
 * 每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。
 * <p>
 * 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），
 * <p>
 * 因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
 * @date 2019/11/13 0013 上午 12:07
 */

public class Code67_RobotMovingCount_回溯 {


    // m行n 列
    public int movingCount(int threshold, int rows, int cols) {
        if (threshold < 0 || rows < 0 || cols < 0) {
            return 0;
        }
        boolean[][] visited = new boolean[rows][cols];
        return doMove(threshold,0,0,rows,cols,visited);
    }

    private int doMove(int threshold, int i, int j, int rows, int cols, boolean[][] visited) {
        if(i < 0 || i >= rows || j < 0 || j >= cols) return 0;
        int count = 0;
        //如果不满足条件的，也要标记为visited
        if(!visited[i][j] && check(threshold,i,j,visited)){
            //当前已经通过，所以count+1
            count = 1 +
                doMove(threshold,i-1,j,rows,cols,visited)+
                doMove(threshold,i+1,j,rows,cols,visited)+
                doMove(threshold,i,j-1,rows,cols,visited)+
                doMove(threshold,i,j+1,rows,cols,visited);
        }
        return count;
    }

    /**
     * 当前位置i，j是否满足要求
     */
    private boolean check(int threshold, int i, int j, boolean[][] visited) {
        visited[i][j] = true;
        return getSum(i) + getSum(j) <= threshold;
    }

    private int getSum(int num) {
        int res = 0;
        while (num != 0){
            res += num % 10;
            num /= 10;
        }
        return res;
    }


}
